1. Field of the Invention
The invention relates generally to RAID controller designs and more specifically relates to improved methods and structure for multi-drive mirroring and striping in a resource constrained RAID controller as for example in RAID level 1E (i.e., Enhanced RAID 1).
2. Discussion of Related Art
It is generally known in the art to utilize RAID storage management methods and structures for high-performance, high-capacity storage subsystems that require high reliability. In a RAID storage subsystem (Redundant Array of Independent Drives), a plurality of disk drives is utilized in accordance with RAID management techniques to improve both reliability and performance of the storage subsystem.
RAID level 0 refers to a RAID management storage technique whereby data stored in the storage subsystem is “striped” across multiple drives. Striping of data involves subdividing the user-supplied data into logical groupings or stripes such that multiple stripes for a portion of the data are distributed over multiple disk drives in the RAID storage array. Each stripe is a physically contiguous portion of the disk drive on which it is stored. Distribution of data stripes over multiple disk drives of the array permits I/O operations for retrieving and storing data to proceed in parallel over multiple disk drives thus improving the subsystem performance for retrieval or storage of data. The I/O operations required to retrieve or store the supplied data are distributed over the multiple disk drives in accordance with the striping methods and structures. By contrast, an equivalent amount of data retrieved or stored on a single disk drive would be slower by a factor approximately proportional to the number of disk drives used in a RAID striping configuration. Striping (RAID level 0) therefore addresses performance issues relating to retrieval or storage of data on a storage subsystem.
Other levels of RAID storage management are associated with improved reliability. For example, RAID level 1 storage management structures and methods duplicate each stripe of data onto at least one additional disk drive. The duplicated data is also commonly referred to as mirrored information. Mirroring of user supplied data over multiple disk drives improves reliability of the storage subsystem in that if a single disk drive of the subsystem is unavailable or otherwise inoperable, the duplicate data stored in a mirrored disk drive is available to continue operation of the storage subsystem. The mirrored data is also more generally referred to as redundant information.
Other levels of RAID storage management techniques provide different forms of redundant information such that loss of a single disk drive in the array does not preclude further operation of the entire storage subsystem.
Another particular form of RAID storage management provides a hybrid approach combining RAID level 0 striping with RAID level 1 mirroring. This particular RAID storage management technique is often referred to as Enhanced RAID 1 or as RAID level 1E. In RAID level 1E storage management, user data is striped over multiple disk drives. The mirrored copy of the user-supplied data is also striped over multiple disk drives but shifted with respect to the initial disk drives such that the original user data stripe and its corresponding mirrored stripe will never be on the same disk drives. RAID level 1E therefore provides the reliability enhancements of RAID level 1 by mirroring user supplied data and provides the performance enhancement of RAID level 0 by striping all user data and corresponding mirrored data across multiple disk drives. RAID level 1E is therefore similar to the reliability provided by RAID level 1 but permits any number of disk drives to be used in the mirroring and striping process (in particular including odd numbers of disk drives).
RAID storage management techniques are typically performed by one or more RAID controllers associated with the RAID storage subsystem. Typically, a RAID storage controller is embedded within the storage subsystem and provides all management of the disk drives of the array. I/O requests are received from host systems coupled to the RAID storage subsystem through the RAID controllers and are processed to store or retrieve identified data to or from the disk drives of the array. RAID storage controllers therefore hide the low-level operation and management of disk drives of the array from the higher level functioning of the host systems. In particular, host systems are generally unaware of what, if any, redundancy is performed within the RAID storage subsystem and what, if any, striping is performed within the RAID storage subsystem. These functions are performed in a manner transparent to the host systems coupled to the RAID controllers.
In general, a RAID controller generates low-level I/O operations for the various disk drives of the array in response to I/O requests received from host systems coupled to the RAID storage subsystem. The low-level I/O operations read or write particular identified data stripes from or to disk drives of the array affected by the host system I/O requests. The overall performance of a RAID storage subsystem is largely dependent on efficient generation and processing of these low-level I/O operations by the RAID controller.
In general, a RAID controller generates a list of low-level I/O operations associated with each disk drive affected by the post system I/O requests being processed. Each such list is typically referred to as a “scatter/gather” list. The entries on the list “scatter” stripes of information to various locations within the disk drive (i.e., in write operations) and the “gather” information from various locations of the disk drive into a memory buffer (i.e., for read operations).
It is beneficial when performing such read or write I/O operations using a scatter gather list that the physical stripes to be read from each disk drive of the array be contiguous in the physical layout of the disk drive. If stripes are to be read from a single disk drive that are not physically contiguous, the I/O requests will complete more slowly because either the controller must separate the requests into two distinct requests or read additional, unnecessary data stripes between the desired non-contiguous stripes. Separating the request into multiple requests avoids the duplicative, unnecessary reading of data stripes but may add latency between the two operations due to disk rotation delays and head seek delays.
FIG. 1 depicts a physical mapping of stripes in an exemplary three disk RAID level 1E subsystem having six rows or stripes on each disk drive. A numeric identifier within the box representing the stripe on the corresponding disk identifies each stripe. The disk drive is identified at the top of the column of stripes as disk drive A (100), disk drive B (102) and disk drive C (104). A corresponding mirrored stripe appears in the physical mapping with a prime (“′”) character associated with the same stripe number.
In accordance with standard RAID level 1E techniques as presently practiced in the art, a “physical stripe” (i.e., physical stripe 0) contains sequential stripe numbers, one for each disk drive of the array (i.e., stripe N, N+1and N+2for a three disk RAID level 1E array). The next physical stripe of the disk array (i.e., physical stripe 1) contains the corresponding mirrored data stripes (i.e., N′, (N+1)′ and (N+2)′) shifted with respect to their respective disk drives such that a stripe and its associated mirrored stripe are never on the same physical drive. These stripes are physically contiguous with corresponding stripes of the preceding physical stripe. For example, as shown in FIG. 1, stripe 0 of physical stripe 0 (110) is contiguous with stripe 2′ of physical stripe 1 (111) on disk drive A (100). in like manner, stripe 1 of physical stripe 0 (110) is contiguous with stripe 0′ of physical stripe 1 (111) on disk drive B (102) and stripe 2 of physical stripe 0 (110) is contiguous with stripe 1′ of physical stripe 1 (111) on disk drive C (104).
Physical stripe 2 (112) contains stripes 3, 4 and 5 on disk drives A, B and C (100, 102 and 104), respectively while physical stripe 3 (113) contains mirrored stripes 5′, 3′ and 4′. Stripes 3 and 5′ are contiguous on disk drive A (100), stripes 4 and 3′ are contiguous on disk drive B (102) and stripes 5 and 4′ are contiguous on disk drive C (104). Physical stripe 4 (114) contains stripes 6, 7 and 8 on disk drives A, B and C (100, 102 and 104), respectively while physical stripe 5 (115) contains mirrored stripes 8′, 6′ and 7′. Stripes 6 and 8′ are contiguous on disk drive A (100), stripes 7 and 6′ are contiguous on disk drive B (102) and stripes 8 and 7′ are contiguous on disk drive C (104).
For a RAID controller to read a single stripe of the array of FIG. 1, a single stripe is read from each of disk drives A, B and C. For example, to read physical stripe 0 comprising stripes 0, 1 and 2, stripe 0 is read from drive A, stripe 1 is read from drive B and stripe 2 is read from drive C. In this simple example, the scatter/gather list for reading from each disk drive consists of a single stripe read. Three I/O operations are generated and tracked and no extraneous (unused) stripes need be read.
However, where multiple stripes need be read, additional I/O operations and/or additional, unused stripes need be read. For example, to read all nine stripes (distributed over three physical stripes) depicted in the physical map of FIG. 1 requires either four I/O operations (four scatter/gather lists) or requires that additional, duplicative stripes be read.
The dashed lines in FIG. 1 indicates noteworthy breaks in the contiguous nature of stripes that may be read without the need for additional I/O operations or duplicative, wasteful reads of stripes. For example, stripes 0 through 5 (i.e., physical stripe 0 (110) and physical stripe 2 (112) cannot be accessed without such duplicative I/O operations or additional low level operations. Likewise, stripes 3 through 8 (i.e., physical stripe 2 (112) and physical stripe 4 (114) cannot be accessed without such duplicative I/O operations or additional low level operations. Still further, it is not possible to access all stripes (0 through 8) without such duplicative waste.
One possible technique to read all stripes in FIG. 1 (i.e., stripes 0 through 8 as shown) would require four I/O operations as follows:
1. A first scatter/gather list for drive A would read physically contiguous stripes 0, 2′, 3, 5′, 6 and 8′.
2. A second scatter/gather list for drive B would read stripe 1.
3. A third scatter/gather list for drive C would read stripe 4′.
4. A fourth scatter/gather list for either drive B or C would read stripe 7 or 7′, respectively, since stripe 7 (or 7′) is not contiguous to any other stripe read from drive B or C.
This sequence of operations requires an additional I/O operation on drive B (or C) to read a stripe not contiguous with any other stripe read from that drive. Generation and tracking of such an additional scatter/gather list can be problematic on a RAID controller constrained in terms of processing and/or memory capacity. To avoid duplicative reading of stripes requires that additional I/O requests be generated and tracked to read non-contiguous portions of at least one drive of the array.
Another possible technique for reading all stripes in the physical map of FIG. 1 would require only two I/O operations as follows:
1. A first scatter/gather list for drive A would read physically contiguous stripes 0, 2′, 3, 5′, 6 and 8′.
2. A second scatter/gather list for drive B would then read contiguous stripes 1, 0′, 4, 3′ and 7.
In this approach, the number of scatter/gather lists and corresponding I/O requests is reduced but at the cost of reading stripe 0′ and 3′ a second time (initially read in the first operation as stripes 0 and 3). The additional reading of these stripes may require extra buffer memory—also a potential problem for resource constrained RAID controllers.
Those skilled in the art will recognize numerous other possible sequences of I/O requests and corresponding scatter/gather list structures to read all physical stripes of the simple example of FIG. 1. However, all such techniques and structures will require either additional low-level I/O requests directed to at least one of the drives and corresponding scatter/gather list maintenance for those drives or will require duplicative, wasteful re-reading of stripes not required for the I/O request processing but required to perform contiguous reads from each disk drive of the array involved in the request.
The above problems similarly relate to write requests to the disks of the array. In fact, the problem is doubled due to the need to write redundant copies of each stripe changed by the write request.
It is evident from the above discussion that a need exists for improved RAID level 1E management to enable effective I/O management in resource constrained RAID controllers.